﻿Random rand = new Random();
int[] arr = new int[10];
for (int i = 0; i < arr.Length; i++)
{
    arr[i] = i;
}
for (int i = 0;i < arr.Length; i++)
{
    int idx = rand.Next(arr.Length);
    int temp = arr[i];
    arr[i] = arr[idx];
    arr[idx] = temp;
}
foreach (int i in arr)
{
    Console.Write(i + " ");
}

QuickSort(arr, 0, 9);
Console.WriteLine();

foreach (int i in arr)
{
    Console.Write(i + " ");
}

int Paritition(int[] arr, int left, int right)
{
    int pivot = arr[left];
    while (left < right)
    {
        while (left < right && arr[right] > pivot)
        {
            right--;
        }
        arr[left] = arr[right];
        while (left < right && arr[left] < pivot)
        {
            left++;
        }
        arr[right] = arr[left];
    }
    arr[left] = pivot;
    return left;
}

void QuickSort(int[] arr, int left, int right)
{
    if (left < right)   // 递归终止条件
    {
        int pivotIndex = Paritition(arr, left, right);
        QuickSort(arr, left, pivotIndex - 1);
        QuickSort(arr, pivotIndex + 1, right);
    }
}

